A Transportation Planning Problem involves determining a cost-optimal way of transporting a set of orders from a set of origins to a set of destinations based on a variety of factors. The factors can include (1) using a transportation network on which different modes, carriers, services and equipments are available for transporting the goods; (2) a rating structure for the transportation service that depends on the mode, carrier, service, and equipment dimensions; (3) flexible or hard time-window constraints on when the orders are to be picked up and delivered, and when the facilities of interest are open for service, pick-up or drop-off; (4) various flexible or hard compatibility constraints such as item-vehicle, facility-facility, item-facility, customer-facility, region-facility and so on.
Three main modes (or types) of trucking carrier exist in the road transportation system. The modes include truckload (TL), less-than-truckload (LTL), and parcel (also known as small package or express). Each mode has a different manner of operation and a different price point. Major U.S. truckload carriers include J.B. Hunt, Schneider National, and Werner Enterprises. Their service involves a shipper essentially hiring truck and a driver to travel between two points. The shipper dictates how the truck gets from the origin to the destination. TL mode offers the lowest rates per unit of cargo but if a truck in not full or nearly-full, smaller shipments or loads can travel more economically via LTL carriers.
LTL carriers like Yellow Freight and Roadway Express typically operate fixed, scheduled hub-and-spoke truck networks over which individual pieces of cargo can travel between various origins and destinations. LTL costs per unit of cargo, while higher than those for nearly-full TL moves, are much lower than those of parcel carriers. Parcel carriers include UPS, FedEx, and DHL.
The transportation planning problem may be thought of as being comprised of two inter-dependent sub-problems, load-building and carrier selection. Load-building involves exploiting economies of scale to achieve lower costs by adopting different simple aggregation strategies as well as complex route-building and hubbing strategies to consolidate smaller shipments into larger loads. Trips are then defined for transporting the loads from a source to a destination. Carrier-selection involves determining the carrier that could service the loads built in load-building resulting in a lowest cost solution subject to carrier-related flexible or inviolable constraints.
In prior systems, an operator would manually assign a carrier to a load simply by selecting the lowest cost carrier for that individual trip. However, when a group of trips are involved, selecting a carrier in this manner may not result in an optimal total cost (e.g. global cost) for the group of trips.